package practise.leetcode.q322;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0) {
            return -1;
        }

        if (amount == 0) {
            return 0;
        }

        int[] dp = new int[amount + 1];
        dp[0] = 0;

        for (int i = 1; i <= amount ; i++) {
            dp[i] = -1;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                int target = i - coins[j];
                if (target < 0) {
                    continue;
                }

                if (dp[target] == -1) {
                    continue;
                }

                int result = dp[target] + 1;
                if (result < min) {
                    min = result;
                }
            }
            dp[i] = min == Integer.MAX_VALUE ? -1 : min;
        }

        return dp[amount];
    }
}
